#include "order_tree.h"
#include "link_tree.h"

void _add_ot(TreeNode** tree, TreeNode* node, CMP cmp)
{
    if (NULL == *tree) {
        *tree = node;
        return;
    }
    if (0 > cmp(node->data,(*tree)->data)) {
        _add_ot(&(*tree)->left, node, cmp);
    }
    else {
        _add_ot(&(*tree)->right, node, cmp);
    }
    cal_height_lt(*tree);
}

void add_ot(TreeNode** tree, void* data, CMP cmp)
{
    _add_ot(tree, create_tn(data, 0), cmp);
}

bool del_ot(TreeNode** tree, void* data, CMP cmp)
{
    if (NULL == *tree)return false;
    if (0 > cmp(data, (*tree)->data)) {
        return del_ot(&(*tree)->left, data, cmp);
    }
    if (0 < cmp(data, (*tree)->data)) {
        return del_ot(&(*tree)->right, data, cmp);
    }
    TreeNode* tmp = *tree;
    *tree = tmp->right;
    if (tmp->left)_add_ot(tree, tmp->left, cmp);
    free(tmp);
    return true;
}

bool mod_val_ot(TreeNode** tree, void* old_data, void* new_data, CMP cmp)
{
    if (del_ot(tree, old_data, cmp)) {
        add_ot(tree, new_data, cmp);
        return true;
    }
    return false;
}

TreeNode* _query_val_ot(TreeNode* tree, void* data, CMP cmp)
{
    if (NULL == tree)return NULL;
    if (0 < cmp(tree->data, data)) {
        return _query_val_ot(tree->left, data, cmp);
    }
    if (0 > cmp(tree->data, data)) {
        return _query_val_ot(tree->right, data, cmp);
    }
    return tree;
}

void* query_val_ot(TreeNode* tree, void* data, CMP cmp)
{
    TreeNode* node = _query_val_ot(tree, data, cmp);
    return node->data;
}

void rdl_last_k_ot(TreeNode* tree, int* index, FUNC show)
{
    if (NULL == tree)return;
    rdl_last_k_ot(tree->right, index, show);
    if (--(*index) == 0)show(tree->data);
    rdl_last_k_ot(tree->left, index, show);
}

TreeNode* prev = NULL;

void _create_cot(TreeNode* tree)
{
    if (!tree)return;
    _create_cot(tree->left);
    //    if(!tree->left){
    //        tree->hasLeftClue = true;
    //        tree->left = prev;
    //    }
    if (prev && !prev->right) {
        prev->hasRightClue = true;
        prev->right = tree;
    }
    prev = tree;
    _create_cot(tree->right);
}

void create_cot(TreeNode* tree)
{
    _create_cot(tree);
}

void clue_cot(TreeNode* tree, FUNC show)
{
    while (NULL != tree) {
        while (NULL != tree->left) {
            tree = tree->left;
        }
        show(tree->data);
        while (tree->hasRightClue) {
            tree = tree->right;
            show(tree->data);
        }
        tree = tree->right;
    }
}

void cal_height_lt(TreeNode* root)
{
    if (!root)return;
    int lh = height_lt(root->left);
    int rh = height_lt(root->right);
    root->height = lh > rh ? lh + 1 : rh + 1;
}
